package com.graph;

import com.collection.Queue;
import edu.princeton.cs.algs4.Stack;

public class DepthFirstOrder {

    private Queue<Integer> pre;
    private Queue<Integer> post;
    private Stack<Integer> reversePost;
    private boolean[] marked;
    public DepthFirstOrder(Graph g) {
        pre = new Queue<>();
        post = new Queue<>();
        reversePost = new Stack<>();

        marked = new boolean[g.V()];

        for (int i = 0 ; i < g.V(); i++) {
            if (!marked[i])
                dfs(g, i);
        }

    }

    private void dfs(Graph g, int v) {

        marked[v] = true;
        pre.enqueue(v);
        for (int w : g.adj(v)) {
            if (!marked[w])
                dfs(g, w);
        }
        post.enqueue(v);
        reversePost.push(v);
    }

    public Iterable<Integer> pre() {
        return pre;
    }

    public Iterable<Integer> post() {
        return post;
    }

    public Iterable<Integer> reversePost() {
        return reversePost;
    }

}
